package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         301,
		Discription: "O(1)时间返回子数组之和",
		Level:       1,
		Labels: map[string]int{
			"前缀和": 1,
		},
	})
}

type NumArray struct {
	prefix []int
	suffix []int
	sum    int
}

func Constructor7(nums []int) NumArray {
	n := len(nums)
	pre := make([]int, n)
	suf := make([]int, n)
	for i := 1; i < n; i++ {
		pre[i] += pre[i-1] + nums[i-1]
	}
	for i := n - 2; i >= 0; i-- {
		suf[i] = suf[i+1] + nums[i+1]
	}
	return NumArray{
		prefix: pre,
		suffix: suf,
		sum:    pre[n-1] + nums[n-1],
	}
}

func (array *NumArray) SumRange(left int, right int) int {
	return array.sum - array.prefix[left] - array.suffix[right]
}
